public class Solution517 {
    public int findMinMoves(int[] machines) {
        int sum = 0, max = 0 ,avg, res, prefix;
        for (int num : machines) {
            sum += num;
            max = Math.max(max, num);
        }
        if(sum % machines.length != 0){
            return -1;
        }
        avg = sum / machines.length;
        res = max - avg;
        prefix = 0;
        for (int i = 0; i<machines.length; i++) {
            prefix += machines[i];
            res = Math.max(res, Math.abs(prefix-(i+1)*avg));
        }
        return res;
    }
}
